%\input{template}
\documentclass[11pt]{article}
%\documentclass{sig-alternate}
\usepackage{algorithm}
\usepackage{algorithmic}

\usepackage{epsfig,amsthm,amsmath,color, amsfonts}
\usepackage{epsfig,color}
\newcommand{\xxx}[1]{\textcolor{red}{#1}}
\usepackage{fullpage}
\usepackage{framed}
%\usepackage{epsf}

\newtheorem{theorem}{Theorem}[section]
%\newtheorem{definition}[theorem]{Definition}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{claim}[theorem]{Claim}
%\newtheorem{example}[theorem]{Example}
\newtheorem{remark}[theorem]{Remark}
\theoremstyle{definition}\newtheorem{example}[theorem]{Example}
\theoremstyle{definition}\newtheorem{definition}[theorem]{Definition}
\theoremstyle{observation}\newtheorem{observation}[theorem]{Observation}

\newcommand{\comment}[1]{}
\newcommand{\QED}{\mbox{}\hfill \rule{3pt}{8pt}\vspace{10pt}\par}
%\newcommand{\eqref}[1]{(\ref{#1})}
\newcommand{\theoremref}[1]{(\ref{#1})}
\newenvironment{proof1}{\noindent \mbox{}{\bf Proof:}}{\QED}
%\newenvironment{observation}{\mbox{}\\[-10pt]{\sc Observation.} }%
%{\mbox{}\\[5pt]}

\def\m{\bar{m}}
\def\eps{{\epsilon}}
\def\half{{1\over 2}}
\def\third{{1\over 3}}
\def\quarter{{1\over 4}}
\def\polylog{\operatorname{polylog}}
\newcommand{\ignore}[1]{}
\newcommand{\eat}[1]{}
\newcommand{\floor}[1]{\left\lfloor #1 \right\rfloor}
\newcommand{\ceil}[1]{\left\lceil #1 \right\rceil}

\newcommand{\algorithmsize}[0]{}

\begin{document}

%\begin{titlepage}
\title{Distributed Random Walks}
%\author{Atish {Das Sarma} \thanks{College of Computing, Georgia Institute of Technology, Atlanta, GA, USA. \hbox{E-mail}:~{\tt atish@cc.gatech.edu, danupon@cc.gatech.edu}} \and Danupon Nanongkai \addtocounter{footnote}{-1}\footnotemark \and Gopal Pandurangan \thanks{Department of Computer Science, Purdue University, West Lafayette, IN 47907, USA.  \hbox{E-mail}:~{\tt gopal@cs.purdue.edu}. Supported in part by NSF Award  CCF-0830476.}}
%\date{}

\maketitle
%\thispagestyle{empty}

%\vspace*{.4in}

%\center{\textbf{Format:} Regular Presentation.}

%\vspace*{.1in}
%Gopal -- use \ell instead of l throughout


%\noindent {\bf Keywords:} Random walks, Random sampling, Distributed algorithm, Metropolis-Hastings sampling.

%\end{titlepage}

\section{Lower bound}
In this section, we consider the {\sc Path-Verification} problem, as
follows.

\textbf{Danupon:} We still have to connect this problem to random
walk. Gopal, could you help with this?

\begin{definition}[{\sc Path-Verification} Problem]
The input of the problem consists of an integer $\ell$, a graph $G$,
and $\ell$ (not necessary distinct) vertices $v_1, v_2, ..., v_\ell$
in $G$. Initially, every node $v_i$ has the interval $[i,i]$. Any
algorithm for this problem proceeds in rounds. In each round, any
node $u$ is allowed the following operation: For each edge $uv$, $u$
can send an interval $[i, j]$ to $v$. The interval $[i, j]$ must be
such that $u$ has all numbers from $i$ to $j$.

For any $i$ and $j$, if any node $u$ has all numbers from $i$ to $j$
then we say that a path $v_i v_{i+1}... v_j$ is verified by $u$. The
goal of this problem is to have the path $v_1v_2...v_\ell$ verified
by some node (in other words, some node has all numbers from $1$ to
$\ell$), using the smallest number of rounds possible. \qed
\end{definition}

We show that there exists a low diameter graph such that any
algorithm for this problem needs roughly $\sqrt{n}$ rounds.

\begin{theorem}
\label{thm:mainLB} For any $n$, there exists a graph $G_n$ of $O(n)$
vertices and diameter $O(\log n)$ such that any algorithm that
solves the {\sc Path-Verification} problem on $G_n$ requires more
than $k$ rounds, where $k=\sqrt{\frac{n}{\log n}}$.
\end{theorem}

We devote the rest of this section to prove the above theorem. Let
us start by defining $G_n$.

\begin{definition}[Graph $G_{n}$] Let $k'$ be an integer such that
$k$ is a power of $2$ and $k'/2\leq 4k < k'$. Let $n'$ be such that
$n'\geq n$ and $k'$ divides $n'$. We construct $G_n$ having
$(n'+2k'-1)=O(n)$ nodes as follows. First, we construct a path
$P=v_1v_2...v_{n'}$. Second, we construct a binary $T$ having $k'$
leaf nodes. Let $u_1, u_2, ..., u_k'$ be it leaves from left to
right. Finally, we connect $P$ with $T$ by adding an edge
$u_iv_{jk'+i}$ for every $i$ and $j$. In the future, we will denote
the root of $T$ by $x$ and its left and right by $l$ and $r$
respectively. The result graph is as in
Figure~\ref{fig:graph_construction}. \qed
\end{definition}

\begin{figure}
  \center
  \includegraphics[width=0.5\linewidth]{Graph_Construction.eps}\\
  \caption{$G_n$}\label{fig:graph_construction}
\end{figure}


Clearly $G_n$ has diameter $O(\log n)$. To prove the theorem, let
$\mathcal A$ be any algorithm for the {\sc Path-Verification}
problem that solves the problem on $G_n$ in at most $k'$ rounds. We
need some definitions and claims to proof the main theorem.


\noindent{\bf Definitions of {\em left/right subtrees} and {\em break points}.}

%Let the root $x$'s two neighbors be $r$ and $l$ (for right and left
%children respectively).
Notice that nodes $v_{jk'+i}$, for all $j$ and $i \leq k'/2$ are in
the subtree rooted at $l$ and all remaining points are in the
subtree rooted at $r$. For any node $v$, let $sub(v)$ denote the
subtree rooted at node $v$. We denote the set of nodes that are
leaves of $sub(l)$ by $L$ (i.e., $L=sub(l)\cap P$) and the set of
nodes that are leaves in $sub(r)$ by $R$.

Since we consider an algorithm that takes $k$ rounds and $k'/2\geq
2k+1$, consider the situation when the algorithm is given $k$ rounds
for {\em free} to communicate only along the edges of the path $P$
at the beginning. Consider the nodes reachable from $L$. Let any
node in $P$ that is not reachable from $L$ (i.e., $v_{jk'+k'/2+i}$,
for all $j$ and $k < i < k'/2-k$) in the initial $k$ rounds be
called a {\em break point} for $sub(l)$. Similarly, any node that is
not reachable from vertices in $R$ be called a {\em break point} for
$sub(r)$. In particular, all nodes of the form $v_{jk'+k'/2+k+1}$,
for all $j$, are break points for $sub(l)$. Let $B_l$ be the set of
such nodes. Similarly all nodes of the form $v_{jk'+k+1}$, for all
$j$ are break points for $sub(r)$ and we let $B_r$ be the set of
such nodes. (See Figure~\ref{fig:breaking-points}.)

\begin{figure}
\center
\includegraphics{breaking-points.eps}
\caption{Breaking points} \label{fig:breaking-points}
\end{figure}

\noindent{\bf Definitions of {\em path-distance} and {\em
covering}.}

For any two nodes $u$ and $v$, let $c(u, v)$ be a lowest common
ancestor of $u$ and $v$. We define $path-dist(u, v)$ to be the
number of leaves of subtree of $T$ rooted at $c(u, v)$. (See
Figure~\ref{fig:path-distance}.)

\begin{figure}
\center
\includegraphics{path-distance.eps}
\caption{Path-distance} \label{fig:path-distance}
\end{figure}

%Let us define the {\em path-distance} between two nodes $v_i$ and
%$v_j$ in $P$ as the distance between $v_i$ and $v_j$ on the path
%$v_1, v_2, \ldots, v_n$. That is $path-dist(v_i, v_j) = |i-j+1|$. We
%also define the path distance between any two nodes in the graph in
%a similar manner: $path-dist(x,y)$ is computed as $2^j$ where $j$ is
%the level of the first common ancestor of $x$ and $y$.

We also introduce the notion of the path-distance {\em covered} by a
message. For any message $m$, the path-distance covered by $m$ is
the maximum path-distance taken over all pairs of nodes that have
held the message $m$.

%\textbf{Danupon:} What does this mean?

\begin{lemma}
\label{lem:one} The number of break points for the left subtree and
for the right subtree are at least $\frac{n}{4k}$ each.
\end{lemma}
\begin{proof}
After the first $k$ free rounds, consider the intervals that the
left subtree can have, in the best case. Recall that these $k$
rounds allowed communication only along the path. The $path-dist$ of
any node in $L$ from the break points of $sub(L)$ along the path is
at least $k+1$.
\end{proof}

The reason we define these break points is to show that the entire
information held by the left subtree has many disjoint intervals,
and same for the right subtree. This then tells us that the left
subtree and the right subtree must {\em communicate} a lot to be
able to merge these intervals by connecting/communicating the break
points.

\begin{lemma}
\label{lem:two} For algorithm $\mathcal A$ to solve {\sc
Path-Verification} problem, the total path-distance covered by all
messages is at least $n$.
\end{lemma}
\begin{proof}
First, notice that each left break point is at a path-distance of
$k+1$ from every node in the right subtree. That is, $path-dist(u,L)
= path-dist(v,R) = k+1$ for all $u\in B_l$ and all $v\in B_r$.

Each break point needs to be connected. However, there could be one
interval that is communicated from the $sub(l)$ to the $sub(r)$ (or
vice versa) such that it connects several break points. We show that
this cannot happen. Consider all the break points $v\in B_l\cup
B_r$.

\noindent{\bf Definition of {\em scratching}}.

Let us say that we {\em scratch out} the break points from the list
$k+1$, $k'/2+k+1$, $k'+k+1$, $k'+k'/2+k+1$, $2k'+k+1$, ... that get
connected when an interval is communicated between $sub(l)$ and
$sub(r)$. We scratch out a break point if there is an interval in
the graph that contains it and both (or one in case of the first and
last break points) its adjacent break points. For example, if the
left subtree has intervals $[1, k'/2+k]$ and $[k'/2+k+2,
k'+k'/2+k+1]$ and the right subtree has $[k+2, k'+k]$ and the latter
interval is communicated to a node in the left subtree, then the
left subtree is able to obtain the merged interval $[1,k'+k'/2+k+1]$
and therefore break points $k+1$ and $k'/2+k+1$ are scratched out.

\begin{claim}
\label{claim:one}
At most $O(1)$ break points can be scratched out with one message/interval communicated between $sub(r)$ and $sub(l)$
\end{claim}
\begin{proof}
We argue that with the communication of one interval across the left
and right subtrees, at most $4$ break points that have not been
scratched yet can get scratched. This follows from a simply
inductive argument. Consider a situation where the left subtree has
certain intervals with all overlapping intervals already merged, and
similarly right subtree. Suppose an interval ${\cal I}$ is
communicated between $sub(r)$ and $sub(l)$, one of few cases arise:
\begin{itemize}
\item ${\cal I}$ contains one break point: Can be merged with at most two other intervals. Therefore, at most three break points can get scratched.
\item ${\cal I}$ contains two break points: Can get connected with at most two other intervals and therefore at most four break points can get scratched.
\item ${\cal I}$ contains more than two break points: The important point is that ${\cal I}$ can contain at most two break points that have not been scratched yet (by definition).
\end{itemize}
This completes the proof of the claim.
\end{proof}

The proof now follows from Lemma~\ref{lem:one}. For any break point
$b$, let $M_b$ be the set of messages the represents an interval
containing $b$ while $b$ is still unscratched. If $b$ is in $sub(l)$
and gets scratched because of the combination of some intervals in
$sub(r)$, then we claim that $M_b$ has covered a path-distance of at
least $k$. (Define the path-distance covered by $M_b$ by the total
path-distance covered by all messages in $M_b$.) This is because $b
= v_i$ (say), being a break point in $sub(l)$ has $i$ equal to $(k+1
\mod k')$. Therefore, $b$ is at a path distance of at least $k$ from
any node in $R$. Consequently, $b$ is at a path-distance of at least
$k$ from any node in $sub(r)$. Since there are
$\Theta(\frac{n}{4k})$ break points, and for any interval to be
communicated across the left and right subtree, a path-distance of
$k$ must be covered, in total, $\Theta(n)$ path-distance must be
covered for all break points to be scratched. This follows from
three main observations:
\begin{itemize}
\item As shown above, for any break point to be scratched, an interval with a break point must
be communicated from $sub(l)$ to $sub(r)$ or vice versa (thereby all messages $m$ containing the
break point together covering a path-distance of at least $k$)
\item Any message/interval with unscratched break points has at most two unscratched break points
\item As shown in Claim~\ref{claim:one}, at most four break points can be scratched when two intervals are merged.
\end{itemize}

The proof follows. (Also see Figure~\ref{fig:scratch_4} for the idea
of this proof.)
\end{proof}

\begin{figure}
\center
\includegraphics{scratch_4.eps}
\caption{Idea of Claim~\ref{claim:one}} \label{fig:scratch_4}
\end{figure}

These intervals can however be communicated using the tree edges as
well. We bound the maximum communication that can be achieved across
$sub(l)$ and $sub(r)$ indirectly by bounding the maximum
path-distance that can be covered in each round. In particular, we
show the following lemma.

\begin{lemma}
\label{lem:three} In $k$ rounds, all messages together can cover at
most a path-distance of $O(k^2\log k)$.
\end{lemma}
\begin{proof}
We consider the total number of messages that can go through nodes
at any level of the graph, starting from level $0$ to level $\log k$
under the congest model.

First notice that if a message is passed at level $i$ of the tree,
this can cover a $path-dist$ of at most $2^i$. This is because the
subtree rooted at a node at level $i$ has $2^i$ leaves. Further, by
our construction, there are $2^{\log (k') - i}$ nodes at level $i$.
Therefore, all nodes at level $i$ together, in a given round of
$\mathcal A$ can cover a $dist-path$, path distance, of at most
$2^i2^{\log (k') - i} = 4k+2$. Therefore, over $k$ rounds, the total
$dist-path$ that can be covered in a single level is $k(k')$. Since
there are $O(\log k)$ levels, the total $path-dist$ that can be
covered in $k$ rounds over the entire graph is $O(k^2\log k)$. See
Figure~\ref{fig:max_path_cover}
\end{proof}

\begin{figure}
\center
\includegraphics{max_path_cover.eps}
\caption{Idea of Lemma~\ref{lem:three}} \label{fig:max_path_cover}
\end{figure}

We now describe the proof of the main theorem using these three claims.

\begin{proof} [Proof of Theorem~\ref{thm:mainLB}]
Use Lemmas~\ref{lem:two} and~\ref{lem:three} we know that if
$\mathcal A$ solves {\sc Path-Verification}, then it needs to cover
a $path-dist$ of $n$, but in $k$ rounds it can only cover a
$path-dist$ of $O(k^2\log k)$. But this is $o(n)$ since
$k=\sqrt{\frac{n}{\log n}}$, contradiction.
\end{proof}
%
%The idea of this proof can be found in Figure~\ref{fig:idea}.
%
%\begin{figure}
%  % Requires \usepackage{graphicx}
%  \includegraphics[width=15cm]{idea.eps}\\
%  \caption{Idea of the proof}\label{fig:idea}
%\end{figure}
%

%
%\newpage
%\appendix
%\section*{Old stuff}
%
%\section{Introduction}
%
%%Random walks are very useful in both
%%theory and practice in many areas in computer science, including
%%distributed computing. Many efficient algorithms perform random
%%walks as a subroutine.
%%Applications in networks include token
%%management~\cite{IJ90, BBF04, CTW93},  checking
%%expander~\cite{DT07}, constructing random spanning trees~\cite{Broder89,
%%BIZ89, BFG+03}, monitoring overlays~\cite{MG07}, group communication in
%%ad-hoc network~\cite{DSW02, SW06}, gathering and dissemination of information
%%over a network \cite{AKL+79}, constructing and doing search
%%in unstructured peer-to-peer networks \cite{GkantsidisMS04},
%%distributed construction of expander networks \cite{LawS03},
%%and peer-to-peer membership
%%management~\cite{GKM03}. They also have been used to provide
%%uniform and efficient solutions to distributed control of dynamic
%%networks \cite{BBSB04}. A further survey of applications of random walks in distributed
%%setting can be found in~\cite{BBSB04}.
%
%Consider a distributed network of processors modeled by an
%unweighted undirected $n$-node graph. Each node corresponds to a
%processor (with  a unique identity number). Initially, each node
%only has its own local perspective of the network; i.e., it only
%knows its own ID and the IDs of its neighbors. Nodes communicate by
%exchanging messages in rounds: In  each round a node can send one
%bit (or at most $B$ bits), per edge. The computation time is
%measured by number of rounds needed. The focus of this paper is to
%study fast distributed algorithms for performing random walks in
%arbitrary networks. We give non-trivial algorithms for performing
%random walks that are significantly faster than the existing (naive)
%approaches.
%
%
%
%\subsubsection*{Problems}
%Although using random walks helps in improving performances of many
%distributed algorithms, all known algorithms perform random walks
%naively: Each walk is performed by sending a token  randomly for
%$\ell$ steps. Is there a faster way to perform a random walk
%distributively? In particular, we consider the following {\em basic}
%random walk problem.
%
%\textit{Computing One Random Walk where Destination Outputs Source.}
%Let $s$ be any node in the network. We want a distributed algorithm
%such that, in the end, one node $v$ outputs the ID of $s$ where $v$
%is randomly picked according to the probability that it is the
%destination of a random walk of length $\ell$ starting at $s$. We
%want an algorithm that finishes in the smallest number of rounds.
%
%We also consider the following generalized versions of the above
%problem.
%\begin{enumerate}
%\item \textit{$k$ Random Walks, Destinations output Sources ($k$-RW-DoS)}: We have $k$ sources
%$s_1, s_2, ..., s_k$ (not necessarily distinct) and we want each of
%$k$ destinations to output an ID of its corresponding source.
%\item \textit{$k$ Random Walks, Sources output Destinations ($k$-RW-SoD)}: Same as above but we want each
%source to output the ID of its corresponding destination.
%\end{enumerate}
%
%%An extension of the first problem can be used in applications where the sources
%%only want to know a ``synopsis'' of the destination, such
%%as aggregating statistics and computing a function (max load, average
%%load) by sampling nodes. The second problem is used when sources want to know data of each
%%destination separately.
%
%\medskip
%\noindent \textbf{Notation:} Throughout the paper, we let $\ell$ be
%the length of the walks, $k$ be the number of walks, $D$ be the
%network diameter,  $\delta$ be the  minimum node degree and $n$ be
%the number of nodes in the network.
%
%%------------------------------------------
%
%\section{Distributing Numbers Game}
%
%
%
%\subsection*{Graph Construction}
%
%We construct an $(n+ {(4K+1)})$ node graph $G_{n,K}$ for parameters
%$n, K$, nodes labeled $\{v_1, v_2, \ldots, v_n\}$ remaining nodes to
%be determined later. Undirected edges include $(v_i, v_{i+1})$ for
%all $i<n$. Therefore, these edges form a line graph. Further, a
%binary tree is imposed on top of these vertices in a special way.
%The result graph is then a diameter $\log K$ graph for a parameter
%$K$. Additional edges. We first describe the additional edges for
%vertices $v_1, \ldots, v_{4K+2}$. These nodes are connected by a
%binary tree above them. That is, we have nodes $v_i^j$ where $j$
%will denote the {\em level}. Assume for simplicity that $4K+2$ is a
%power of two (ACTUALLY THIS CAN NEVER BE TRUE - SO TO MAKE IT $4K+4$
%LATER ON AND REST GOES THROUGH SAME WAY). Node $v_1^1$ connects to
%$v_1$ and $v_2$. Similarly $v_i^1$ (for $i\leq 2k+1$) connects to
%$v_{2i-1}$ and $v_{2i}$. Similarly nodes in level $j$ are
%constructed. So $v_i^j$ is connected to $v_{2i-1}^{j-1}$ and
%$v_{2i}^{j-1}$. Here, $j$ goes from $1$ to $\log (4K+2)$ and $i$ at
%level $j$ goes from $1$ to $2^{\log (4K+2) - j}$. Denote the root of
%this binary tree by $x$. Notice that nodes $v_1, v_2, \ldots,
%v_{2K+1}$ are on the left subtree of $x$ and $v_{2K+2}, \ldots,
%v_{4K+2}$ are on the right subtree of $r$.
%
%The connection of the remaining nodes $v_{4K+3}, v_{4K+4}, \ldots,
%v_n$ is similar. Any node $v_i$ with $i\geq (4K+3)$ has edges to the
%same nodes as $v_j$ for $j = (i \mod 4K+2)$ for $1\leq j\leq
%(4K+2)$.
%
%\subsection*{Problem Definition}
%
%We now describe the problem {\sc DiscoverPath}. To start with, every
%node $v_i$ has the interval $[i,i]$, i.e. only containing the point
%$i$. Any node is allowed the following operations:
%\begin{itemize}
%\item It can send the interval(s) it has to neighbors (in one round).
%\item If it has/receives a set of intervals, it may combine intersecting intervals. That is, if node has $[i_1, j_1]$ and $[i_2, j_2]$ and $i_1\leq i_2\leq j_1\leq j_2$, then it can combine these to form one interval $[i_1, j_2]$.
%\end{itemize}
%
%The problem of {\sc DiscoverPath} is for any node in the graph to
%eventually have the interval $[1,n]$. We now state the main theorem
%of this section.
%
%\section{Connecting Simpler Problem to Random Walks}
%
%\section{Improved Upper Bound}
%
%  \let\oldthebibliography=\thebibliography
%  \let\endoldthebibliography=\endthebibliography
%  \renewenvironment{thebibliography}[1]{%
%    \begin{oldthebibliography}{#1}%
%      \setlength{\parskip}{0ex}%
%      \setlength{\itemsep}{0ex}%
%  }%
%  {%
%    \end{oldthebibliography}%
%  }
%{ \small
%\bibliographystyle{plain}
%%\bibliographystyle{alpha}
%\bibliography{Distributed-RW}

%\newpage
%\appendix
%\section{Applications}

\end{document}
